/* 组合计数
    乘法原理，加法原理，组合数，排列数
* 1.常用方法-隔板法
    n个小球，n-2个板子 插入到n-1个空隙中，有C n-1 k-1种方法

* 本题:
    高精度组合数计算
*/

#define DEBUG
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 150, MOD = 1000; //最大位数
int x, k;
int f[1000][100][N]; //C(i, j)的高精度表示数组

int qmi(int base, int index, int MOD)
{
    int res = 1;
    while(index)
    {
        if(index & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        index >>= 1;
    }
    return res;
}

void add(int c[], int a[], int b[]) //c=a+b 高精度加法
{
    for(int i = 0, t = 0; i < N; i++)
    {
        t += a[i] + b[i];
        c[i] = t % 10;
        t /= 10;
    }
}

signed main()
{
    #ifdef DEBUG
        freopen("./in.txt", "r", stdin);
    #else
        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    cin >> k >> x;

    int n = qmi(x % MOD, x, MOD); //爆int, 需要先模int

    //printf("%d %d\n", n, k);
    // C(n-1, k-1)
    for(int i = 0; i < n; i++) //上标i
        for(int j = 0; j <= i && j < k; j++) //下标j
            if(!j) f[i][j][0] = 1; //C(i,0) = 1
            else add(f[i][j], f[i-1][j], f[i-1][j-1]); //f[i][j] = f[i-1][j] + f[i-1][j-1];
            //C(i, j) = C(i - 1, j) + C(i - 1, j - 1)

    int *g = f[n-1][k-1];
    int i = N-1;
    while(!g[i]) i--; //找到首个不为0的元素
    while(i >= 0) cout << g[i--];
    return 0;
}
